package stack_test;

import java.util.*;

/**
 * 全排列1
 * 使用递归回溯的思想
 */
public class leetcode46 {

}
class Solution1 {
    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> ret = new ArrayList<>();
        if(nums.length == 0){
            return ret;
        }

        //path即一个栈，用来存储数字，used即判断是否已经列举
        Deque<Integer> path = new ArrayDeque<>();
        //默认为false
        boolean[] used = new boolean[len];

        //调用深度优先搜索
        dfs(nums,len,0,path,used,ret);
        deleteUnique(ret);
        return ret;
    }

    public void dfs(int[] nums,int len,int depth,Deque<Integer> path,boolean[] used,List<List<Integer>> ret){
        if(depth == len){
            ret.add(new ArrayList<>(path));
            return;
        }
        for(int i=0; i < len; i++){
            //被使用了
            if(used[i] == true){
                continue;
            }else {
                path.addLast(nums[i]);
            }
            used[i] = true;
            dfs(nums,len,depth+1,path,used,ret);
            path.removeLast();
            used[i] = false;
        }
    }
    public void deleteUnique(List<List<Integer>> ret){
        //利用hashset进行去重的操作
        Set<List<Integer>> set = new HashSet<>();
        for (int i = 0; i < ret.size(); i++) {

            List<Integer> list = ret.get(i);

            set.add(list);
        }

        ret.clear();
        //迭代器遍历
        /*
        Iterator<List<Integer>> iterator = set.iterator();
        while (iterator.hasNext()){
            ret.add(iterator.next());
        }
         */
        //增强循环遍历
        for(List<Integer> element : set){
            ret.add(element);
        }
    }
}
